The present invention relates to a method for prefetching data, which is contained in a so-called pointer-type data structure consisting of a plurality of elementary data each including data and addresses of other data.
The performance of processors has been improved recently, whereas the speed of memory did not follow. Then there have been methods for improving the performance of an information processing apparatus by using cache memory. As cache memory stores only a copy of part of main memory, there may be or not desired data in the cache memory (cache miss hit). In such case, the processor has to wait until the data is read out from the main memory, for starting next processing. This causes overhead cycles. There have been proposed a variety of methods for avoiding this overhead. Data prefetching method is one of them. The concept of this method is to store in advance into the cache memory data which may result in cache misses prior to use them. In this method, the performance of the information processing apparatus may be improved by performing prefetching of data from main memory to cache memory and other processes in parallel.
For the data prefetching method, Callahan et. al., "Software Prefetching," ASPLOS-IV Proceedings, April 1991, pp. 40-52 discusses known hardware prefetching methods, and proposes a software prefetching method as a better solution. For example, one of the previously known hardware prefetching methods is to use a circuit for prefetching one of lines when the last address of the immediately previous line in the cache is accessed. On the other hand, in software prefetching, an instruction is performed to prefetch and store in the cache memory data which are expected to be accessed by a software prior to its actual access.
The reference cited above teaches that the software prefetching may be applied to, for example, an array-type data structure. The array-type data structure comprises data stored in memory locations of a plurality of addresses which are continuous or spaced-apart by a given address interval. This allows the address of the next data to be fetched to be determined prior to actual reading of its array-type data structure by using the address of the data at the leading location of that array-type data structure and the address spacing. Thus the next data to be read out may be loaded in the cache memory by preliminarily instructing from software.
In addition, there has been proposed hardware capable of prefetching such an array-type data structure. For example, in the reference No. 2: "Architecture and evaluation of Ocyanomizu-1." research report for information processing society, Computer Architecture 101-8, Aug. 20, 1993, pp. 57-64, a processor reads an array-type data structure from main memory before using that array-type data structure to load and store it in a buffer memory for prefetching, provided in addition to cache memory such that the processor may read any elementary data in the array-type data structure from the buffer for prefetching, when processing the data element. The time to load the array data from main memory is not apparently seen from the processor.
One of data structure frequently used in software other than the array-type data structure is a pointer-type data structure, which has structure connected by pointers. The pointer-type data structure viewed from software is shown in FIG. 6, and an example of this type of data structure allocated in the main memory is shown in FIG. 7. Each of the elementary data 10, 20, and 30 constituting such data structures includes a plurality of entries 11-14, 21-24, and 31-34, and each elementary data comprises a pointer specifying successive elementary data in one of entries such as 11, 21, and 31. In the example shown in FIG. 7 the pointer is the address of the successive elementary data.
For reading a plurality of elementary data classified into the pointer-type data structure from memory 90, a load instruction for reading the leading elementary data such as 10 from a memory 90 is initially performed to thereby read that leading elementary data from memory. Then a plurality of instructions for processing data contained within respective entries 12-14 of that elementary data are performed. Thereafter, from the memory location having the address of the second elementary data contained in the leading entry 11, another load instruction is issued for fetching next elementary data. Thus the addresses of the elementary data except the leading data is found when the preceding elementary data is fetched from memory.
Therefore, in the method of software prefetching referenced in the reference No. 1, the prefetching is expected not to be much effective for the pointer-type data structure.
The reference No. 2 explains a method for performing hardware prefetching for the array data, however no explanation is disclosed for the method how to perform hardware prefetching for the pointer-type data structure or other structures. Thus, there was no method for prefetching applied to the pointer-type data structure in the Prior Art.
The pointer-type data structure is not only frequently used by programs written in list processing languages but also frequently used by operating systems. Therefore, in order to improve the speed performance of operating systems, it is preferable to improve the time needed for fetching the pointer-type data structure.